package com.jinan.algorithm.Combinatorics;

/**
 * 给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
 * **线性扫描**
 * <p>
 * 示例 1：
 * 输入：nums = [1,2,3]
 * 输出：6
 * <p>
 * 示例 2：
 * 输入：nums = [1,2,3,4]
 * 输出：24
 * <p>
 * 示例 3：
 * 输入：nums = [-1,-2,-3]
 * 输出：-6
 */
public class MaxProduct {
    public static void main(String[] args) {
        int[] nums = {-10, -10, 5, 2};
        System.out.println(maxProduct(nums)); // 输出: 500
    }

    public static int maxProduct(int[] nums) {
        int max1 = Integer.MIN_VALUE;
        int max2 = Integer.MIN_VALUE;
        int max3 = Integer.MIN_VALUE;
        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MAX_VALUE;
        for (int num : nums) {
            if (num > max1) {
                max3 = max2;
                max2 = max1;
                max1 = num;
            }else if (num > max2) {
                max3 = max2;
                max2 = num;
            }else if (num > max3) {
                max3 = num;
            }
            if (num < min1) {
                min2 = min1;
                min1 = num;
            }else if (num < min2) {
                min2 = num;
            }
        }
        return Math.max(max1 * max2 * max3, min1 * min2 * max1);
    }
}
